// https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
// 17. 电话号码的字母组合
// 中等
// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (!digits) {
    return []
  }

  const map = {
    2: 'abc'.split(''),
    3: 'def'.split(''),
    4: 'ghi'.split(''),
    5: 'jkl'.split(''),
    6: 'mno'.split(''),
    7: 'pqrs'.split(''),
    8: 'tuv'.split(''),
    9: 'wxyz'.split('')
  }

  const arr = digits.split('').map(item => map[item] || [])
  const res = []

  const maxLevel = arr.length

  // 回溯法
  const helper = (subsets, level) => {
    // 到达树的底部
    if (level === maxLevel) {
      res.push(subsets.join(''))
      return
    }

    const cur = arr[level]

    // 回溯算法框架
    for (let i = 0; i < cur.length; i++) {
      const ch = cur[i]

      // 做选择
      subsets.push(ch)
      // 递归下一层回溯树
      helper(subsets, level + 1)
      // 撤销选择
      subsets.pop()
    }
  }
  helper([], 0)

  return res
}

console.log(
  letterCombinations('23')
)
